package _01_排序;

import java.util.Arrays;

/*
    快速排序,本质上是一个二叉树的前序遍历
    选择轴点元素排好序，不断的按照先序方式排序每一个轴点元素
 */
public class QuickSort {
    public static void sort(int[] nums){
        sort(nums,0,nums.length-1);
    }

    //函数定义:不断将数组化分成子数组，对每个轴点元素进行判断
    private static void sort(int[] nums,int lo,int hi){
        if(lo >= hi) return; //只有一个就不用排序

        int pivotIndex = partition(nums,lo,hi); //划分数组并将第一个轴点元素排好序

        //对nums[lo,p-1]排序
        sort(nums,lo, pivotIndex - 1);
        //对nums[p+1,hi]排序
        sort(nums, pivotIndex +1,hi);

    }

    //对nums[lo...hi]进行切分并且将轴点元素排好序
    private static int partition(int[] nums,int lo,int hi){
        //随机交换begin位置的元素，随机选择轴点元素，降低最坏时间复杂度
        //范围是 [lo,hi]
        swap(nums,lo,(lo +(int)(Math.random())*(hi - lo)));
        int pivot = nums[lo]; //待排序的轴点元素,数组第一个元素

        while(lo<hi){
            while(lo<hi){
                //从右向左比,当前元素大于轴点元素就向左移动
                if(cmp(pivot,nums[hi])<0){
                    hi--;
                }else{
                    //将小于轴点元素的当前元素放在左半部数组，从改变方向
                    nums[lo++] = nums[hi];
                    break;
                }
            }
            while(lo<hi){
                if(cmp(pivot,nums[lo])>0){
                    lo++;
                }else{
                    nums[hi--] = nums[lo];
                    break;
                }
            }
        }
        //排完序后，此时begin = end就是轴点元素所在的位置,将轴点元素放入轴点的位置
        nums[lo] = pivot;
        return lo;
    }

    private static int cmp(int i,int j){
        return i - j;
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{5,-2,-4,6,80,45,36,21,99,66};
        sort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
